class node(object):
    value = None
    parent = None

    def __init__(self, _parent, _value):
        self.value = _value
        self.parent = _parent


def find_ladders(begin_word, end_word, word_list):
    pre = [node(None, begin_word)]
    cur = []
    while True:
        cur = find(pre, word_list)
        if arrive(cur, end_word):
            break
        pre = cur
        cur = []
    arrivals = []
    for i in cur:
        if i.value == end_word:
            arrivals.append(i)
    paths = []
    for i in arrivals:
        path = []
        while True:
            if i.parent != None:
                path.append(i.value)
                i = i.parent
            else:
                break
        path.append(begin_word)
        paths.append(path)
    for i in xrange(len(paths)):
        paths[i] = paths[i][::-1]
    print paths


def arrive(now, end):
    for i in now:
        if i.value == end:
            return True
    return False


def find(pre, words):
    cur = []
    for i in pre:
        for word in words:
            if if_one_diff(i.value, word):
                cur.append(node(i, word))
    return cur


def if_one_diff(word_a, word_b):
    diff_count = 0
    for i in xrange(len(word_a)):
        if word_a[i] != word_b[i]:
            diff_count += 1
    return True if diff_count == 1 else False


begin_word = 'hit'
end_word = 'cog'
word_list = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
find_ladders(begin_word, end_word, word_list)
